package code;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class BB {
	public String largestNumber(int[] num) {
		
		List<String> list=new ArrayList<String>();
		int i;
		int n=num.length;
		for(i=0;i<n;i++){
			list.add(String.valueOf(num[i]));
		}
		Collections.sort(list, new Comparator<String>(){

			/*
			 * ���ľ�������
			 * 3,30��300,��Щ��Ӧ�ð���ʲô��������
			 * �Ǿ�ֱ�ӱȽϽ��ķ���a+b��b+a�Ƚϣ��Ǹ����ţ���ѡ����һ��
			 */
			
			@Override
			public int compare(String a, String b) {
				// TODO Auto-generated method stub
				String ab=a+b;
				String ba=b+a;
				long c=Long.parseLong(ab)-Long.parseLong(ba);
				return (int)c;
			}
			
		});
		String res="";
		for(i=n-1;i>=0;i--){
			res+=list.get(i);
		}

		/*
		 * remove leading 0
		 */
		StringBuilder sb=new StringBuilder(res);
		for(i=0;i<sb.length();i++){
			if(sb.charAt(i)!='0')	break;
		}
		if(i==sb.length()) res="0";
		else res=sb.substring(i, sb.length());
        return res;
    }
	/*
	 * ������ֱ���������ټ��㡣��Ȼ�������ĿҪ��
	 */
    public int maximumGap(int[] num) {
    	List<Integer> list=new ArrayList<Integer>();
    	int n=num.length;
    	for(int i=0;i<n;i++){
    		list.add(num[i]);
    	}
    	Collections.sort(list);
    	int maxGap=0;
    	for(int i=0;i<n-1;i++){
    		if(list.get(i+1)-list.get(i)>maxGap)
    			maxGap=list.get(i+1)-list.get(i);
    	}
        return maxGap;
    }
    /*
     * Ͱ��˼��
     * ���е���ֲ���Max-min�����֮��
     * ����ֳ�Max-min/(size-1)�Σ�ÿ�α�ʾһ��Ͱ
     * �����е��ź������֮���ֵ avg=(Min-min)/(size-1)
     * ��maxGap<avg�Ļ����Ǹ�maxGap*(size-1)<Min-min,ì��
     * ����maxGap>=avg
     * ���ԣ�maxGap��ȡֵһ���ڲ�ͬ��Ͱ��֮��Tongmax,Tongmin��ȡֵ
     */
    public int maximumgapII(int[] num){
    	int n=num.length;
    	
    	if(n<2) return 0;
    	if(n==2)	return Math.abs(num[1]-num[0]);
    	int[] maxList=new int[n-1];
    	int[] minList=new int[n-1];

    	int maxGap=0;
    	int max,min;
    	int i,j;
    	max=0;
    	min=Integer.MAX_VALUE;
    	for(i=0;i<n;i++){
    		if(max<num[i])	max=num[i];
    		if(min>num[i])	min=num[i];
    		if(i==n-1)	break;
    		maxList[i]=0;
    		minList[i]=Integer.MAX_VALUE;
    	}
    	int bucketLen=(max-min)/(n-1);
    	bucketLen+=1;
    	for(i=0;i<n;i++){
    		num[i]-=min;
    		int bucket=num[i]/bucketLen;
    		if(maxList[bucket]<num[i])	maxList[bucket]=num[i];
    		if(minList[bucket]>num[i]) minList[bucket]=num[i];
    	}
    	maxGap=maxList[0]-minList[0];
    	for(i=1;i<n-1;i++){
    		/*
    		 * �յ�Ͱ��Ҫ����
    		 */
    		for(j=i;j<n-1;j++){
    			if(minList[j]!=Integer.MAX_VALUE)	break;
    		}
    		if(j==n-1)	break;
    		if(maxGap<minList[j]-maxList[i-1])
    			maxGap=minList[j]-maxList[i-1];
    		i=j;
    	}
        return maxGap;
    }
    
    public int findPeakElement(int[] num){
    	int ans=0;
    	int n=num.length;
    	if(n<=1)	return ans;
    	for(int i=0;i<num.length;i++){
    		if(i==0 && num[i]>num[i+1])
    			return i;
    		if(i==n-1 && num[i]>num[i-1])
    			return i;
    		if(i>0 && i<n-1 && num[i]>num[i-1] && num[i]>num[i+1])
    			return i;
    					
    	}
    	return ans;
    }
    
    static class ListNode{
    	int val;
    	ListNode next;
    	ListNode(int x){
    		val=x;
    		next=null;
    	}
    }
    /*
     * ��������ת����
     */
    public ListNode ReverseLinkList(ListNode head){
    	/*
    	 * ֻ��һ��Ԫ�ص�ʱ��,ֱ�ӷ���head
    	 */
    	if(head.next==null)	return head;
    	ListNode a,b,c;
    	c=head;
    	b=null;
    	a=null;
    	while(c!=null){
    		a=b;
    		b=c;
    		c=c.next;
    		b.next=a;
    	}
    	b.next=a;
    	head=b;
		return head;
    }
    public ListNode findTail(ListNode head){
    	ListNode p,q;
    	p=head;
    	if(p==null)	return null;
    	while(p.next!=null){
    		p=p.next;
    	}
    	return p;
    }
    public ListNode getIntersectionNodeII(ListNode headA,ListNode headB){
    	ListNode p=headA;

    	while(p!=null){
    		if(p==headB)	break;
    		p=p.next;
    	}
    	if(p!=null)	return p;
    	if(headA==null || headB==null)	return null;
    	ListNode tailA=findTail(headA);
    	ListNode tailB=findTail(headB);
    	if(tailA!=tailB)	return null;
    	
    	/*
    	 * to do tailA.next=null;
    	 */
    	tailA.next=headB;
    	ListNode q=headA;
    	p=headA;
    	do{
    		p=p.next;
    		q=q.next.next;
    	}while(p!=q);
    	/*
    	 * q��ѭ���㣬ѭ�����
    	 */
    	p=headA;
    	while(p!=q){
    		p=p.next;
    		q=q.next;
    	}
    	tailA.next=null;
    	return q;
    }
    /*
     * ��������������кʹ���0�������
     */
    public int canComlepteCircuit(int[] gas,int[] cost){
    	int res=-1;
    	int n=gas.length;
    	int[] Gas=new int[2*n];
    	int[] Cost=new int[2*n];
    	int i,j;
    	for(i=0;i<n;i++){
    		Gas[i]=Gas[i+n]=gas[i];
    		Cost[i]=Cost[i+n]=cost[i];
    	}
    	int max=0,index=0,ans=-1;
    	for(i=0;i<2*n;i++){
    		max+=Gas[i]-Cost[i];
    		if(max<0){
    			max=0;
    			index=i+1;
    		}
    		if(i-index==n-1 && max>=0){
    			return index;
    		}
    	}
    	max=0;
    	index=2*n-1;
    	for(i=2*n-1;i>=0;i--)
    	{
    		max+=Gas[i]-Cost[i];
    		if(max<0){
    			max=0;
    			index=i-1;
    		}
    		if(index-i==n-1 && max>=0){
    			return index-n;
    		}
    	}
    	return -1;
    }
	public static void main(String[] args){
		BB bb=new BB();
		int[] num={1, 2, 3, 1};
//		System.out.println(bb.findPeakElement(num));
	}
}
